#include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define MAXVEX 20

typedef unsigned char VertexType;
typedef unsigned int EdgeType;
bool visited[MAXVEX] = {false};

typedef struct EdgeNode
{
	VertexType adjvex;
	EdgeType weight;
	struct EdgeNode *next;
}EdgeNode;

typedef struct VertexNode
{
	VertexType data;
	EdgeNode *firstedge;
}VertexNode;

typedef struct
{
	VertexNode adjList[MAXVEX];
	int numVertexes;
	int numEdges;
}GraphAdjList;

VertexType vertexArray[MAXVEX][MAXVEX]={
/* 0 */ {0, 1, 0, 0, 0, 1, 1, 0, 0},
/* 1 */ {1, 0, 1, 0, 0, 0, 0, 0, 0},
/* 2 */ {0, 1, 0, 1, 0, 0, 0, 0, 0},
/* 3 */ {0, 0, 1, 0, 1, 0, 0, 1, 0},
/* 4 */ {0, 0, 0, 1, 0, 1, 0, 0, 1},
/* 5 */ {1, 0, 0, 0, 1, 0, 0, 0, 0},
/* 6 */ {1, 0, 0, 0, 0, 0, 0, 1, 1},
/* 7 */ {0, 0, 0, 1, 0, 0, 1, 0, 1},
/* 8 */ {0, 0, 0, 0, 1, 0, 1, 1, 0}
};

void CreateGraphAdjList(GraphAdjList *GL)
{
	VertexType i,j;
	for(i=0; i < GL->numVertexes; ++i)
    {
        GL->adjList[i].data = i;
    }
	for(i=0; i<GL->numVertexes; ++i)
    {
        EdgeNode **pEN = &(GL->adjList[i].firstedge);
        for(j=0; j<GL->numVertexes; ++j)
        {
            if(vertexArray[i][j])
            {
                *pEN = (EdgeNode *)malloc(sizeof(EdgeNode));
                (*pEN)->adjvex = j;
                pEN = &(*pEN)->next;
            }
        }
        *pEN = NULL;
    }
}

void DFS(GraphAdjList GL, int i)
{
    EdgeNode *p;
    visited[i] = true;
    printf("%d ", GL.adjList[i].data);
    p = GL.adjList[i].firstedge;
    while(p)
    {
    	if(!visited[p->adjvex])
    		DFS(GL, p->adjvex);

    	p = p->next;
    }
}


void DFSTraverse(GraphAdjList GL)
{
	for (int i = 0; i < GL.numVertexes; ++i)
		visited[i] = false;

	for (int i = 0; i < GL.numVertexes; ++i)
		if (!visited[i])
			DFS(GL, i);
}

int main(int argc, char const *argv[])
{
	GraphAdjList *GL = (GraphAdjList*)malloc(sizeof(GraphAdjList));
	GL->numVertexes = 9;
	CreateGraphAdjList(GL);
	DFSTraverse(*GL);
	return 0;
}

